home *** CD-ROM | disk | FTP | other *** search
/ Amiga Collections: Den Norske Hjemmedataklubben / Amiga-Hack 93-1 (1993)(Data-Tronic AS)(NO)(Disk 2 of 2)[b dump].zip / Amiga-Hack 93-1 (1993)(Data-Tronic AS)(NO)(Disk 2 of 2)[b dump].adf / BROWSER / PATMATCH.C < prev    next >
C/C++ Source or Header  |  1992-12-15  |  6KB  |  265 lines
  1. /* PatMatch.c - Implements AmigaDos Regular Expression Pattern Matching.
  2. **
  3. **  This program will test whether a string is an AmigaDos  regular expression
  4. **  It may be used to implement wild expressions such as:
  5. **
  6. **    "copy #?.c to <dir>" to copy any file ending in .c
  7. **
  8. **  The program has two entry points: CmplPat, and Match.
  9. **
  10. **    CmplPat - takes a pattern and returns an auxilliary integer vector
  11. **              which is used by Match.  The pattern is not modified in
  12. **              any way.  CmplPat returns 1 if no errors were detected
  13. **              while compiling the pattern; otherwise it returns 0;
  14. **
  15. **    Match   - takes the pattern, the auxilliary vector, and the string
  16. **              to be matched.  It returns 1 if the string matches the
  17. **              pattern; otherwise it returns 0;
  18. **
  19. **  Translated from BCPL by:
  20. **              Jeff Lydiatt
  21. **              Richmond B.C. Canada
  22. **              16 May 1986.
  23. **
  24. **  Source: "A Compact Function for Regular Expression Pattern Matching",
  25. **           Software - Practice and Experience, September 1979.
  26. **
  27. **  Useage:
  28. **     To test if "file.c" matches the regular expression "#?.c"
  29. **     char *Pat = "#?.c";
  30. **     char *Str = "file.c";
  31. **     WORD Aux[128];
  32. **
  33. **     if ( CmplPat( Pat, Aux ) == 0 )
  34. **        {
  35. **           printf("Bad Wildcard Expression\n");
  36. **           exit(1);
  37. **        }
  38. **     if ( Match( Pat, Aux, Str ) == 1 )
  39. **        printf("String matches the pattern\n");
  40. **     else
  41. **        printf("String does NOT match the pattern\n");
  42. **/
  43.  
  44. /*--- Included files ----*/
  45.  
  46. #include <stdio.h>
  47. #include <exec/types.h>
  48. #include <ctype.h>
  49.  
  50. #define  EOS '\0'
  51.  
  52. /*--- Global Variables  ---*/
  53.  
  54. static char     Ch;      /* The current character in Pattern */
  55. static char     *Pat;    /* Pointer to the Pattern */
  56. static WORD     *Aux;    /* Pointer to returned auxilliary vector */
  57. static int      PatP;    /* Current position in Pat */
  58. static int      Patlen;  /* strlen(pat) */
  59. static BOOL     Errflag; /* TRUE if error */
  60. static WORD     *Work;   /* Pointer to Active work area */
  61. static int      Wp;      /* Current position in work */
  62. static BOOL     Succflag;/* True if "str" matches "pat" */
  63.  
  64. /*----------------------------------------------------------------*/
  65. /*                   The Interpreter                              */
  66. /*----------------------------------------------------------------*/
  67.  
  68. static void Put(int N)
  69. {
  70.    register WORD *ip;
  71.    register WORD *to;
  72.  
  73.    if ( N == 0 )
  74.       Succflag = TRUE;
  75.    else
  76.       {
  77.     for ( ip = &Work[ 1 ], to = &Work[ Wp ]; ip <= to; ip++)
  78.        if ( *ip == N )
  79.           return;
  80.     Work[ ++Wp ] = N;
  81.       }
  82. }
  83.  
  84. int Match( char *Pat, WORD *Aux, char *Str )
  85. {
  86.    static WORD W[ 128 ];
  87.    int  S = 0;
  88.    int  I, N, Q, P, Strlength;
  89.    char K;
  90.    int  strlen();
  91.    void Put();
  92.  
  93.    Work = W;
  94.    Wp = 0;
  95.    Succflag = FALSE;
  96.    Strlength = strlen( Str );
  97.    Put( 1 );
  98.  
  99.    if ( Aux[ 0 ] != 0 )
  100.       Put( Aux[ 0 ] );
  101.  
  102.    for(;;)
  103.       {
  104.         /* First complete the closure */
  105.         for( N=1; N <= Wp; N++ )
  106.           {
  107.          P = Work[ N ];
  108.          K = Pat[ P-1 ];
  109.          Q = Aux[ P ];
  110.          switch( K )
  111.            {
  112.           case '#': Put( P + 1 );
  113.           case '%': Put( Q );
  114.           default : break;
  115.           case '(':
  116.           case '|': Put( P + 1);
  117.                 if ( Q != 0 )
  118.                    Put( Q );
  119.         }
  120.        }
  121.  
  122.     if ( S >= Strlength )
  123.        return Succflag;
  124.     if ( Wp == 0 )
  125.        return FALSE;
  126.     Ch = Str[ S++ ];
  127.  
  128.     /* Now deal with the match items */
  129.  
  130.     N = Wp;
  131.     Wp = 0;
  132.     Succflag = FALSE;
  133.  
  134.     for ( I = 1; I <= N; I++)
  135.       {
  136.          P = Work[ I ];
  137.          K = Pat[ P - 1 ];
  138.          switch( K )
  139.            {
  140.          case '#':
  141.          case '|':
  142.          case '%':
  143.          case '(': break;
  144.          case '\'': K = Pat[ P ];
  145.          default : if ( _toupper( Ch ) != _toupper( K ) )
  146.                   break;
  147.          case '?': /* Successful match */
  148.                 Put ( Aux[ P ] );
  149.         } /* End Switch */
  150.       } /* End For I */
  151.      } /* End for(;;) */
  152. }
  153.  
  154.  
  155. /*----------------------------------------------------------------*/
  156. /*                     The Compiler                               */
  157. /*----------------------------------------------------------------*/
  158.  
  159. static void  Rch(void) /* Read next character from Pat */
  160. {
  161.    if ( PatP >= Patlen )
  162.       Ch = EOS;
  163.    else
  164.       Ch = Pat[ PatP++ ];
  165. }
  166.  
  167. static void Nextitem(void) /* Get next char from Pat; recognize the ' escape char */
  168. {
  169.    if ( Ch == '\'' )
  170.       Rch();
  171.    Rch();
  172. }
  173.  
  174. static void Setexits( int List, int Val )
  175. {
  176.    int A;
  177.  
  178.    do
  179.      {
  180.     A = Aux[ List ];
  181.     Aux[ List ] = Val;
  182.     List = A;
  183.      }
  184.     while ( List != 0 );
  185. }
  186.  
  187. static int Join( int A, int B )
  188. {
  189.     int T = A;
  190.  
  191.     if ( A == 0 )
  192.     return B;
  193.     while ( Aux[ A ] != 0 )
  194.     A = Aux[ A ];
  195.     Aux[ A ] = B;
  196.     return T;
  197. }
  198.  
  199. static int Prim(void)      /* Parse a Prim symbol */
  200. {
  201.    int   A = PatP;
  202.    char Op = Ch;
  203.    int  Exp();
  204.    void Setexits(), Nextitem();
  205.  
  206.    Nextitem();
  207.    switch( Op )
  208.      {
  209.         case EOS:
  210.         case ')':
  211.         case '|': Errflag = TRUE;
  212.         default : return A;
  213.         case '#': Setexits( Prim(), A ); return A;
  214.         case '(': A = Exp( A );
  215.           if ( Ch != ')' )
  216.             {
  217.             Errflag = TRUE;
  218.             }
  219.           Nextitem();
  220.           return A;
  221.      }
  222. }
  223.  
  224. static int Exp( int AltP )    /* Parse an expression */
  225. {
  226.    int Exits = 0;
  227.    int A;
  228.    int Prim(), Exits(), Join();
  229.    void Nextitem(), Setexits();
  230.  
  231.    for (;;)
  232.     {
  233.        A = Prim();
  234.        if ( Ch == '|' || Ch == ')' || Ch == EOS )
  235.           {
  236.         Exits = Join( Exits, A );
  237.         if ( Ch != '|' )
  238.            return Exits;
  239.         Aux[ AltP ] = PatP;
  240.         AltP = PatP;
  241.         Nextitem();
  242.           }
  243.        else
  244.           Setexits( A, PatP );
  245.     }
  246. }
  247.  
  248. int CmplPat( char *Pattern, WORD *CmplPattern)
  249. {
  250.    int i, strlen();
  251.    void Rch(), Setexits();
  252.  
  253.    Pat = Pattern;
  254.    Aux = CmplPattern;
  255.    PatP = 0;
  256.    Patlen = strlen( Pat );
  257.    Errflag = FALSE;
  258.  
  259.    for ( i = 0; i <= Patlen; i++ )
  260.       Aux[ i ] = 0;
  261.    Rch();
  262.    Setexits( Exp(0), 0 );
  263.    return (!Errflag);
  264. }
  265.